{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook was prepared by [Donne Martin](http://donnemartin.com). Source and license info is on [GitHub](https://github.com/donnemartin/interactive-coding-challenges)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Solution Notebook"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Problem: Implement merge sort.\n",
    "\n",
    "* [Constraints](#Constraints)\n",
    "* [Test Cases](#Test-Cases)\n",
    "* [Algorithm](#Algorithm)\n",
    "* [Code](#Code)\n",
    "* [Unit Test](#Unit-Test)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Constraints\n",
    "\n",
    "* Is a naive solution sufficient?\n",
    "    * Yes\n",
    "* Are duplicates allowed?\n",
    "    * Yes\n",
    "* Can we assume the input is valid?\n",
    "    * No\n",
    "* Can we assume this fits memory?\n",
    "    * Yes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test Cases\n",
    "\n",
    "* None -> Exception\n",
    "* Empty input -> []\n",
    "* One element -> [element]\n",
    "* Two or more elements\n",
    "* Left and right subarrays of different lengths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algorithm\n",
    "\n",
    "Wikipedia's animation:\n",
    "![alt text](http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif)\n",
    "\n",
    "* Recursively split array into left and right halves\n",
    "* Merge split arrays\n",
    "    * Using two pointers, one for each half starting at index 0\n",
    "        * Add the smaller element to the result array\n",
    "        * Increment pointer where smaller element exists\n",
    "    * Copy remaining elements to the result array\n",
    "    * Return result array\n",
    "\n",
    "Complexity:\n",
    "* Time: O(n log(n))\n",
    "* Space: O(n)\n",
    "\n",
    "Misc:\n",
    "\n",
    "* Not in-place\n",
    "* Most implementations are stable\n",
    "\n",
    "Merge sort can be a good choice for data sets that are too large to fit in memory, as large chunks of data can be read and written to disk.\n",
    "\n",
    "Unlike many other sorting algorithms, merge sort is not done in-place.\n",
    "\n",
    "See: [Quicksort vs merge sort](http://stackoverflow.com/questions/70402/why-is-quicksort-better-than-mergesort)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from __future__ import division\n",
    "\n",
    "\n",
    "class MergeSort(object):\n",
    "\n",
    "    def sort(self, data):\n",
    "        if data is None:\n",
    "            raise TypeError('data cannot be None')\n",
    "        return self._sort(data)\n",
    "\n",
    "    def _sort(self, data):\n",
    "        if len(data) < 2:\n",
    "            return data\n",
    "        mid = len(data) // 2\n",
    "        left = data[:mid]\n",
    "        right = data[mid:]\n",
    "        left = self._sort(left)\n",
    "        right = self._sort(right)\n",
    "        return self._merge(left, right)\n",
    "\n",
    "    def _merge(self, left, right):\n",
    "        l = 0\n",
    "        r = 0\n",
    "        result = []\n",
    "        while l < len(left) and r < len(right):\n",
    "            if left[l] < right[r]:\n",
    "                result.append(left[l])\n",
    "                l += 1\n",
    "            else:\n",
    "                result.append(right[r])\n",
    "                r += 1\n",
    "        # Copy remaining elements\n",
    "        while l < len(left):\n",
    "            result.append(left[l])\n",
    "            l += 1\n",
    "        while r < len(right):\n",
    "            result.append(right[r])\n",
    "            r += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unit Test\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Overwriting test_merge_sort.py\n"
     ]
    }
   ],
   "source": [
    "%%writefile test_merge_sort.py\n",
    "from nose.tools import assert_equal, assert_raises\n",
    "\n",
    "\n",
    "class TestMergeSort(object):\n",
    "\n",
    "    def test_merge_sort(self):\n",
    "        merge_sort = MergeSort()\n",
    "\n",
    "        print('None input')\n",
    "        assert_raises(TypeError, merge_sort.sort, None)\n",
    "\n",
    "        print('Empty input')\n",
    "        assert_equal(merge_sort.sort([]), [])\n",
    "\n",
    "        print('One element')\n",
    "        assert_equal(merge_sort.sort([5]), [5])\n",
    "\n",
    "        print('Two or more elements')\n",
    "        data = [5, 1, 7, 2, 6, -3, 5, 7, -1]\n",
    "        assert_equal(merge_sort.sort(data), sorted(data))\n",
    "\n",
    "        print('Success: test_merge_sort')\n",
    "\n",
    "\n",
    "def main():\n",
    "    test = TestMergeSort()\n",
    "    test.test_merge_sort()\n",
    "\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    main()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "None input\n",
      "Empty input\n",
      "One element\n",
      "Two or more elements\n",
      "Success: test_merge_sort\n"
     ]
    }
   ],
   "source": [
    "%run -i test_merge_sort.py"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
